Content delivery networks (CDNs) deploy surrogate origin servers, also referred to as caching servers or edge servers, at various points-of-presence (PoPs) that are geographically proximate to large numbers of end users. Each PoP includes multiple edge servers. These edge servers deliver content from various content providers to the geographically proximate end users. The overall end user experience is improved as the resources of the CDN often exceed those of the content providers such that the edge servers can respond to the end user requests more expediently and by virtue of the geographic proximity that the edge servers have to the end users, the requested content is delivered with less latency, jitter, packet loss, etc. than if the same content was otherwise delivered from more distant origin servers of the content providers.
End user content requests that are routed to a particular PoP are distributed across the edge servers of that particular PoP. This distribution primarily serves to partition the load across the edge servers of the particular PoP. How effectively the load is partitioned depends on how effectively the requests are distributed across the edge servers.
A round-robin distribution is a basic scheme in which the edge servers of a PoP are ordered and each incoming content request is distributed to the next edge server in the ordering. This ensures that the edge servers receive an equal amount of content requests. Advantages of the round-robin distribution scheme include its simplicity in terms of resource overhead (e.g., processing and memory) and efficient computation. The round-robin distribution scheme operates without consideration of the content being requested such that the incoming content requests need not be processed. A simple lookup as to the next available server is all that is required to distribute the requests. This allows for a relatively underpowered server to distribute thousands of requests per second and prevents the distribution element within the PoP or network from becoming a bottleneck.
However, the equal distribution of requests provided by any round-robin distribution scheme is less than ideal in the context of a CDN. Each distributed request can consume different amounts of server resources. Consequently, the equal distribution of requests can fail to produce an equal partitioning of load across the edge servers of a PoP. Round-robin distribution is also not a consistent distribution scheme. A first request for particular content may be routed to a first edge server of a PoP and a second request for the same particular content may be routed to a second edge server of a PoP, even though the first edge server may have the particular content already in cache as a result of the first request. Consequently, content is redundantly cached within the PoP (at the first edge server and the second edge server), thereby leading to inefficient usage of storage resources and reduction in the overall cache footprint of a PoP (i.e., overall amount of content that the PoP can cache). Overall performance of the PoP is also reduced as a result of the edge servers having to perform more cache writes and purges when redundantly caching content. Lastly, round-robin distribution results in a higher cache miss ratio. The higher cache miss ratio stems from the distribution schemes inability to guarantee that subsequent requests for the same content are distributed to the same edge server that has previously cached that content. For these and other reasons, round-robin distribution does not provide a well-balanced partitioning of load across edge servers of a PoP.
To address the problems stemming from redundant caching, many CDNs have utilized consistent distribution schemes to distribute content requests amongst edge servers of a PoP. A consistent distribution scheme, such as the Cache Array Routing Protocol (CARP), divides the space of hosted content amongst the edge servers of a specific PoP and ensures that requests for the same content are routed to the same edge server of the specific PoP. This often involves hashing an identifier that uniquely identifies the content being requested to identify the edge server tasked with servicing that content, wherein the hashing consistently identifies the same edge server for the same identifier. The identifier typically includes the Uniform Resource Locator (URL) or some permutation thereof, such as a Uniform Resource Identifier (URI) and Fully Qualified Domain Name (FQDN) as some examples. Other parameters such as the requesting end user's IP address and port combination can also be used as part of the hash.
While consistent distribution schemes have effectively eliminated redundant caching of content in a PoP and the performance impact associated with redundant caching, actual analysis of consistent distribution schemes in use today has revealed a tradeoff between evenness and efficiency of the request distribution produced by these distribution schemes. For instance, CARP is a lightweight efficient distribution scheme that can efficiently distribute thousands of requests, but CARP does so at the expense of a relative uneven distribution. The uneven distribution then results in a poor partitioning of load amongst edge servers in a PoP. Other consistent distribution schemes that rely on cryptographic hashes have produced more even request distributions than CARP. However, these schemes are computationally taxing on the server performing the distribution because of the complexities of the cryptographic hashes. As such, these distribution schemes are unsuitable for use in a CDN framework in which thousands of incoming requests have to be distributed in a short period of time (e.g., few seconds).
To quantify the shortcomings of CARP, FIG. 1 presents results for an actual distribution of requests when using a consistent hashing technique implemented per the CARP specification. The distribution is presented for three different content types across edge servers of two CDN PoPs. In this figure, field 110 represents the total number of requests of a specific content type that a particular PoP distributes during the monitored period. Field 120 represents the fewest requests of a specific content type that any edge server of a particular PoP receives as a result of the CARP distribution. Field 130 represents the most requests of a specific content type that any edge server of the particular PoP receives as a result of the CARP distribution. Field 140 presents the median number of requests of a specific content type received by the edge servers of a particular PoP. Field 150 presents the standard deviation for the number of requests of a specific content type received by the edge servers of a particular PoP. Lastly, field 160 presents the average time needed to process an incoming request, wherein processing the incoming request includes computing the hash from which the distribution decision is based.
As evident from the distribution of requests presented in FIG. 1, CARP does not provide an even distribution. Specifically, the least utilized edge server receives approximately 25% of the number of requests as the most utilized edge server in a given PoP. When considering that the requests are for the same content type, it can be extrapolated that the least utilized edge server receives a quarter of the load as the most utilized edge server in a given PoP. This uneven distribution causes certain edge servers to be overutilized and others to be underutilized.
One factor behind the uneven distribution produced by CARP is the use of an inadequate hash. The hashes called for in the CARP specification are selected for their computational efficiencies. However, this focus on efficiency produces the uneven distribution shown in FIG. 1. The obvious solution involves replacing the simplistic CARP hashes with more robust hashes. For instance, cryptographic hashes, such as SHA1, can be used to provide a more even distribution. However, cryptographic hashes and other robust hashes incur substantially greater processing overhead, thus rendering these hashes unsuitable for use in a CDN framework.
A second factor behind the uneven distribution is the “one-size fits all” approach to request distribution. Specifically, the same hash is used to distribute “hot” content and “not hot” content. Hot content is content that is requested frequently during a period of time and not hot content is content that is requested infrequently during that period of time. Accordingly, an edge server that receives requests for hot content will be overutilized when compared to an edge server that receives requests for not hot content. Also, the CARP specification does not consider the content that is being requested and the same hash functions are used to distribute different content types irrespective of the disparate load requirements that the different content types may impose on the edge servers. For instance, servicing requests for large file content consumes greater resources of an edge server than servicing requests for small file content. This is because of the additional bandwidth, memory, processing, and connection overhead needed to transmit the larger file. Accordingly, an edge server that receives a disproportionate number of large file content requests will be overutilized when compared to an edge server that receives a disproportionate number of small file content requests.
An even load partition is critical in order to achieve maximum resource utilization in a PoP and the request distribution scheme used is the primary factor in determining these loads. When the request distribution scheme produces an unbalanced load distribution, it will cause the entire capacity of the PoP to be reduced. For example, a PoP with an unbalanced load distribution in which one edge server operates at 95% capacity with other edge servers operating around 60% of capacity will be able to service substantially fewer requests than a PoP with a balanced load distribution in which all edge servers operate at 90% capacity. Accordingly, there is a need for an improved content request distribution scheme. Specifically, there is a need for a scheme that avoids redundant caching in a PoP while providing for a distribution of requests that results in an even partitioning of load amongst edge servers of that PoP. Also, there is a need for such a scheme to remain lightweight and computationally efficient so as to be able to receive, process, and distribute several thousand requests per second.